1. Field of the invention
The present invention relates to a digital image processing system, and more specifically to a system for depicting a line segment on a display image memory.
2. Description of related art
A conventional line segment depicting system will be described with reference to the accompany drawing.
FIG. 1A shows an ideal line segment defined on a fine two-dimensional coordinate plane, and FIG. 1B shows an approximate line segment obtained by developing the line segment of FIG. 1A onto a discrete coordinate grid. A display memory is deemed as being a two-dimensional plane based on a discrete coordinate system. Therefore, in order to depict a line segment on the display, it is necessary to develop or convert the ideal line segment of FIG. 1A to the approximate line segment of FIG. 1B. This means that when the approximate line is a deemed as being a collection or set of dots, a dot string {X.sub.N, Y.sub.N } on the discrete coordinate system is obtained.
More specifically, an integer coordinate system is introduced as the discrete coordinate system of FIG. 1B. The following is one typical conventional method for developing the ideal line segment of FIG. 1A given with a start point coordinate (X.sub.S, X.sub.Y) and an end point coordinate (X.sub.E, Y.sub.E) in order to uniquely define the line segment on the coordinate plane, onto the integer coordinate system as shown in FIG. 1B.
First, the ideal line is classified into eight kinds, on the basis of an angle .alpha. between a directional vector of the ideal line segment and a direction of +X. As shown in FIG. 2, th value of .alpha. is divided in units of 45 degrees. For example, if 0.degree..ltoreq..alpha.&lt;45.degree., the ideal line segment is called as a "line segment whose directional vector included in a first octant". Similarly, if 45.degree..ltoreq..alpha.&lt;90.degree., the ideal line segment is called as a "line segment whose directional vector included in a second octant". Therefore, all ideal line segments having a length of 2 or more are included in any of first to eight octants. However, in order to determine in which octant the ideal line is included, it is not necessary to actually calculate the angle .alpha.. It is possible to classify the line segment, by discriminating a positive/negative sign of three equations: X.sub.E -X.sub.S, Y.sub.E -Y.sub.E -Y.sub.S, and (X.sub.E X.sub.S)-(Y.sub.E - Y.sub.S).
Here, the line segment included in the first, fourth, fifth or eighth octant will be called as an "X-major line segment", and the line segment included in the second, third, sixth or seventh octant will be called as a "Y-major line segment". In addition, in the X-major line segment, an X component will be called a "major component" and a Y component will be called a "minor component". In the Y-major line segment, an X component will be called a "minor component" and a Y component will be called a "major component".
Now, a process to sequentially obtain each point coordinate (X.sub.n, Y.sub.n) of the dot string {X.sub.N, Y.sub.N } on the integer coordinate system as the approximate line segment will be described with reference to FIG. 3. FIG. 3 illustrates an example of a line segment included in the first octant. The ideal line segment shown in FIG. 3 is sampled at each coordinate point of the integer X coordinate. Here, it is assumed that a preceding sampling point is (X.sub.n-1, Y.sub.n-1) and a current sampling point is (X.sub.n, Y.sub.n). For the current sampling point C, a fraction of the Y coordinate value Yr, namely, an error between the ideal line segment and the approximate line segment is sought. If the error is less than 0.5, it is deemed that Y.sub.n =Y.sub.n-1. If the error is not less than 0.5, it is deemed that Y.sub.n =Y.sub.n-1 +1. This means that an integer coordinate point (X.sub.n, Y.sub.n) nearest to (X.sub.n, Y.sub.r) is obtained. In FIG. 3, a point A and another point B are shown as an integer coordinate point near to (X.sub.n, Y.sub.r), but since the error is not less than 0.5, Y.sub.n =Y.sub.n- 1 +1 is adopted. Namely, the point A is selected.
The recurrence formula of the major component is ceaselessly X.sub.n =X.sub.n+1. On the other hand, the recurrence formula of the minor component is either Y.sub.n =Y.sub.n-1 or Y.sub.n =Y.sub.n-1 +1, depending upon the value of the error. In ordinary cases, a threshold value of the error is set to 0.5, so that if the error is less than 0.5, Y.sub.n =Y.sub.n-1 is selected, and if the error is not less than 0.5, Y.sub.n =Y.sub.n-1 +1 is selected. The latter will be called as "carry-up by DDA error item". In other words, if there is no carry-up by DDA error item, the minor component will not change, and if the error item changes, the minor component will change.
The above is an explanation about X-major line segment included in the first octant. In the cases of other octants, the recurrence formula is somewhat different. The following table shows a relation of each octant and the associated recurrence formula
TABLE 1 ______________________________________ Increment/decrement of minor component Increment/decrement when DDA error item Octant of major component is carried up ______________________________________ 1st octant X.sub.n = X.sub.n-1 + 1 Y.sub.n = Y.sub.n-1 + 1 2nd octant Y.sub.n = Y.sub.n-1 + 1 X.sub.n = X.sub.n-1 + 1 3rd octant Y.sub.n = Y.sub.n-1 + 1 X.sub.n = X.sub.n-1 - 1 4th octant X.sub.n = X.sub.n-1 - 1 Y.sub.n = Y.sub.n-1 + 1 5th octant X.sub.n = X.sub.n-1 - 1 Y.sub.n = Y.sub.n-1 - 1 6th octant Y.sub.n = Y.sub.n-1 - 1 X.sub.n = X.sub.n-1 - 1 7th octant Y.sub.n = Y.sub.n-1 - 1 X.sub.n = X.sub.n-1 + 1 8th octant X.sub.n = X.sub.n-1 + 1 Y.sub.n = Y.sub.n-1 - 1 ______________________________________
The line segments included in the first, fourth, fifth and eighth octants are the X-major line segments, and the line segments included in the second, third, sixth and seventh octants are the Y-major line segments. In the case of the Y-major line segment, the line segment is sampled on the basis of the integer Y coordinate, and the X coordinate value Xr at each sampling point is obtained so that the nearest integer coordinate point (X.sub.n, Y.sub.n) is obtained.
The above mentioned method is called a DDA (Digital Differential Analyzer), and is one of the most general methods for depicting a line segment in a discrete XY coordinate system such as in a display memory. In practice, the DDA using the integer type Bresenham algorithm in which the fraction discrimination is placed with an integer sign discrimination is used. The DDA and the integer type Bresenham algorithm are described in detail in "Procedural Elements for Computer Graphics" by David F. Rogers.
In the above mentioned conventional line segment depicting system, when an ideal line segment having a sampling point having the error of 0.5 is converted into an approximate line, the following problem has been encountered. An approximate line obtained by putting the start point and the end point at (X.sub.S, Y.sub.S) and at (X.sub.E, Y.sub.E), respectively, is not consistent with another approximate line obtained by putting the start point and the end point at (X.sub.E, Y.sub.E) and at (X.sub.S, Y.sub.S), respectively.
The problem will specifically be explained with reference to FIG. 4. FIG. 4A illustrates, by black dots, an approximate line having the start point of (-2, -1) and the end point of (6, 3). approximate line is obtained by using a DDA mechanism adopting an error discrimination condition that when the error item is not less than 0.5, the carry-up is performed. On the other hand, FIG. 4B illustrates, by black dots, an approximate line having the start point of (6, 3) and the end point of (-2, -1), which is obtained by the same DDA mechanism. As seen from comparison between FIGS. 4A and 4B, the solid line of FIG. 4B is a simple replacement of the start point and the end point of the solid line of FIG. 4A by the end point and the start point, respectively, but the black dot patterns of FIG. 4A and 4B are not consistent. This means that the trace of the approximate line depicted or stored in the display memory is different. The line segment on the two-dimensional plane should be uniquely determined on the basis of two opposite ends of the line segment, without changing by exchanging the start point and the end point. However, if the trace of the approximate line depicted or stored in the display memory becomes different by exchanging the start point and the end point for the end point and the start point, respectively, an excessive load is given on a graphic software.
The above mentioned error discrimination condition is that when the error item is not less than 0.5, the carry-up is performed. However, the problem similarly occurs even if the error discrimination condition is changed to that when the error item is greater than 0.5, the carry-up is performed. In the case that the error item is greater than 0.5, the carry-up is performed, FIG. 4A illustrates an approximate line having the start point of (6, 3) and the end point of (-2, -1), and FIG. 4B illustrates an approximate line having the start point of (-2, -1) and the end point of (6, 3). Similarly, the depicted traces are not consistent.
In order to make the depicted traces on the display memory consistent, the following method has been proposed in the prior art. Namely, a line segment depicting system has been configured such that the error discrimination condition can be selected from two different conditions: .a first error discrimination condition that when the error item is not less than 0.5, the carry-up is performed and a second error discrimination condition that when the error item is greater than 0.5, the carry-up is performed. However, in any case, it is necessary to discriminate in which octant a given line segment is included, by means of a graphic software, so that it is determined which of the two error discrimination conditions should be used for depicting the approximate line segment. This discrimination has to be performed for each line segment, and the result of the determination has to be notified to the line segment depicting apparatus. Therefore, the depicting speed lowers inevitably.